Various programming tools perform static program analyses, for example, to better optimize, understand, or browse computer programs.
Software compilers, as one example of a programming tool, compile source code in a source language into target code in a target language. The target code may be executed directly by a data processing system or linked by a suitable linker with other target code for execution by the data processing system.
To help improve the execution of target code by the data processing system, one typical compiler performs optimization techniques based on the expected run-time usage of memory locations for the compiled program as defined by a store model or storage shape graph. The compiler may generate the store model by performing a pointer analysis to determine the effects of program statements referencing memory locations with constants, variables, or functions, for example.
One method used by typical programming tools to perform static program analyses, such as a pointer analysis for example, is type inference. Type inference methods for pointer analyses define types to approximate the run-time usage of memory locations for a program.
Polymorphic type inference methods, unlike monomorphic type inference methods, distinguish among the values of parameters passed to and from a function at different call sites in a program and may therefore be used for pointer analyses to represent a relatively more accurate approximation of the run-time usage of memory locations for the program. Indeed, typical polymorphic type inference methods, such as Henglein's semi-algorithm as described, for example, in Henglein, F., "Type Inference with Polymorphic Recursion," ACM Transactions on Programming Languages and Systems, Vol. 15, No. 2, pp. 253-289 (April 1993), may be used to infer a best possible or principal typing of the program. Because the principal typing for some programs is infinite in size, however, typical polymorphic type inference methods have limited application because they will not terminate in inferring types for such programs.